class Solution
{
public:
    int t;
    vector<int> ans;
    vector<vector<int>> ret;
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        t = target;
        dfs(candidates, 0, 0);
        return ret;
    }
    void dfs(vector<int> &candidates, int sum, int pos)
    {
        if (sum == t)
        {
            ret.push_back(ans);
            return;
        }
        if (sum > t || pos == candidates.size())
            return;
        for (int i = pos; i < candidates.size(); i++)
        {
            if (sum + candidates[i] > t)
                continue;
            ans.push_back(candidates[i]);
            // 注意这里的传递的参数是i
            dfs(candidates, sum + candidates[i], i);
            ans.pop_back();
        }
    }
};

class Solution {
public:
    int t;
    vector<int> ans;
    vector<vector<int>> ret;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        t=target;
        dfs(candidates,0,0);
        return ret;
    }
    void dfs(vector<int>&candidates,int sum,int pos)
    {
        if(sum==t)
        {
            ret.push_back(ans);
            return;
        }
        if(sum>t||pos==candidates.size()) return;
        for(int i=0;sum+candidates[pos]*i<=t;i++)
        {
            if(i) ans.push_back(candidates[pos]);
            dfs(candidates,sum+candidates[pos]*i,pos+1);
            //不能在这里进行回溯因为我们每一层的每个分支一次只加了一个数字
            //如果我们这里回溯了进入下个分支还是只加了一个数字
            //可是下一个分支要把上一个分支多一个数字的
          
        }
        //一层分支走完进行回溯·
        for(int i=1;sum+candidates[pos]*i<=t;i++)
        {
            ans.pop_back();
        }
    }
};


class Solution {
public:
    int t;
    vector<int> ans;
    vector<vector<int>> ret;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        t=target;
        dfs(candidates,0,0);
        return ret;
    }
    void dfs(vector<int>&candidates,int sum,int pos)
    {
        if(sum==t)
        {
            ret.push_back(ans);
            return;
        }
        if(sum>t||pos==candidates.size()) return;
        for(int i=0;sum+candidates[pos]*i<=t;i++)
        {
           for(int j=0;j<i;j++)
           {
            ans.push_back(candidates[pos]);
           }
            dfs(candidates,sum+candidates[pos]*i,pos+1);
          for(int j=0;j<i;j++)
          {
            ans.pop_back();
          }
          
        }
       
    }
};